/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package pathfinder;

/**
 *
 * @author ayo
 */
/** This BinaryTree implementation borrowed from: http://my.cs.lmu.edu/~pdorin/BinaryTree.java */

public class BinaryTree implements java.util.Collection
{
   private Node node;
   private int size;

   //Empty Binary Tree
   public BinaryTree ()
   { 
      node = null;
      size = 0;
   }

   //Binary Tree with single root node.
   public BinaryTree ( Object rootData)
   { 
      node = new Node ( rootData, new BinaryTree(), new BinaryTree() ); 
      size = 1;
   }

   
   // Constructs a binary tree consisting of a new root node and two binary trees. 
   public BinaryTree ( Object rootData, BinaryTree leftSubtree, BinaryTree rightSubtree )
   {
      node = new Node ( rootData, leftSubtree, rightSubtree );
      size = 1 + node.leftST.size + node.rightST.size;
   }


   // Static factory for binary trees. 	   
   public static BinaryTree fromData ( Object rootData, BinaryTree left, BinaryTree right )
   {
      return new BinaryTree ( rootData, left, right );
   }
   
   // Re-initializes this to an empty binary tree.
   public void clear () { node = null; size = 0; }  
	
	
   /** Returns the number of nodes in this binary tree. */
   public int size () { return size; }


   public boolean isEmpty () { return size == 0; }


   public int hashCode ()
   {
      return super.hashCode(); 
   }
   

   /** Returns an iterator for this binary tree which visits the nodes in preorder. 
	   All bets are off if the tree changes during the traversal. */
	   
   public java.util.Iterator PreIterator ()
   {
      if ( size  == 0 ) { return new EmptyTreeIterator(); }
      else { return new PreorderIterator( this ); }
   }
   
   public java.util.Iterator iterator ()
   {
      return PreIterator();
   }

	
   /** Returns an iterator for this binary tree which visits the nodes in inorder. 
	   All bets are off if the tree changes during the traversal. */
	   
   public java.util.Iterator InOrderIterator () {
      if ( size  == 0 ) { return new EmptyTreeIterator(); }
      else { return new InorderIterator( this ); }
   }

   	
  /** Returns an array consisting of references to this tree's objects, visited 
       in preorder. */

   public Object[] toArray ( Object[] a ) {
      Object[] result = new Object[this.size()];
	  int i = 0;
	  for ( Object o : this ) { result[i] = o; i++; }
	  return result;
   }


   /** Adds a node (say, X), which is decorated with obj, to this binary tree, 
	   returning a success flag. Node X becomes the root of the tree; the former 
	   tree becomes X's left subtree; X's right subtree will be empty. */

   public boolean add ( Object o ) {
      
      // Make a duplicate root node:
      BinaryTree newRoot = new BinaryTree(node.obj,node.leftST,node.rightST);
	  
	  // Update what was the root node:
	  node.obj = o;
	  node.leftST = newRoot;
	  node.rightST = new BinaryTree();
	  size++;
	  return true;
   }

   /** Adds a node (say, X), which is decorated with obj, to this binary tree, 
	   returning a success flag. Node X becomes the root of the tree; the former 
	   tree becomes X's right subtree; X's left subtree will be empty. */

   public boolean add2 ( Object o ) {
   
      // Make a duplicate root node:
      BinaryTree newRoot = new BinaryTree(node.obj,node.leftST,node.rightST);
	  
	  // Update what was the root node:
	  node.obj = o;
	  node.leftST = new BinaryTree();
	  node.rightST = newRoot;
	  size++;
	  return true;
   }
   public boolean remove ( Object obj ) {
      throw new UnsupportedOperationException();
   }

	
   /** Removes all matching objects from this binary tree, returning a success flag. 
      The matching object must be (at) a leaf; if there is no matching leaf,
	  then the method returns false. Not supported at this time. */

   public boolean removeAll (  java.util.Collection c ) {
      throw new UnsupportedOperationException ();
   }

 	

   /** This adds all members of Collection c to this binary tree. */

   public boolean addAll ( java.util.Collection c ) {
      java.util.Iterator it = c.iterator();
	  while ( it.hasNext() ) { this.add ( it.next() ); }
	  return true;
   }


   /** Returns true iff this binary tree contains (at least) one example
       of Object obj. */

   public boolean contains ( Object o ) {
      java.util.Iterator it = this.PreIterator();
	  while ( it.hasNext() ) {
	     if ( o.equals( it.next() ) ) { return true; }
	  }
	  return false;
   }

   /** Returns true iff this binary tree contains at least one example of each DIFFERENT
       object in Collection c, i.e., although c may contain several examples of some 
       (same) object, this binary tree is only required to contain one such example. */

   public boolean containsAll ( java.util.Collection c ) {
      java.util.Iterator it = c.iterator();
	  while ( it.hasNext() ) {
	     if ( ! this.contains ( it.next() ) ) { return false; }
	  }
	  return true;
   }
   
   public boolean retainAll (  java.util.Collection c ) {
      throw new UnsupportedOperationException ();
   }
	

   // Private helper method for toString():

   private String toString ( String spaces ) {
      return
	    spaces + node.obj.toString() + "\n"
		+ ( ( node.leftST.size == 0 ) ? ( spaces + "  (empty)\n" ) : ( node.leftST.toString( spaces + "  " ) ) )
		+ ( ( node.rightST.size == 0 ) ? ( spaces + "  (empty)\n" ) : ( node.rightST.toString( spaces + "  " ) ) );
   }
   
   /** Returns a string representation of this binary tree. */

   public String toString () {
      if ( size == 0 ) { return "(empty)"; }
      else { return this.toString(""); } // see private helper method, above
   }
  

   /** Returns an array with a reference to each object in this tree. */

   public Object[] toArray () {
      Object[] objectArray = new Object [size];
      java.util.Iterator it = this.PreIterator();
	  int index = 0;
	  while ( it.hasNext() ) {
	     objectArray[index] = it.next() ;
		 index++;
	  }
	  return objectArray;
   }



   // Helper class that represents tree nodes:

   class Node {
	  private Object obj;			// the object that decorates this node
	  private BinaryTree leftST;	// a reference to the left subtree
	  private BinaryTree rightST;	// a reference to the right subtree

	  public Node () { throw new UnsupportedOperationException(); }
	  
	  public Node ( Object data, BinaryTree left, BinaryTree right ) {
		obj = data; 
		leftST = ( left == null ) ? new BinaryTree() : left; 
		rightST = ( right == null ) ? new BinaryTree() : right;
	  }

   }


   // Helper class implementing an iterator for an empty tree:

   class EmptyTreeIterator implements java.util.Iterator {
   
      public EmptyTreeIterator () { }
   
	  public boolean hasNext () { return false; }
      
	  public Object next () { throw new java.util.NoSuchElementException(); }
      
	  public void remove () { throw new UnsupportedOperationException(); }
   }


   // Helper class representing a preorder iterator for non-empty trees:

   class PreorderIterator implements java.util.Iterator {

      private java.util.Stack<BinaryTree> stack;
   
      public PreorderIterator ( BinaryTree bt ) {
		 stack = new java.util.Stack<BinaryTree>();
         stack.push ( bt );
      }

      public boolean hasNext () {
         return ! stack.empty();
      }

      public Object next () {
	     if ( stack.empty() ) { throw new java.util.NoSuchElementException(); }
         BinaryTree current = stack.pop();
	     if ( current.node.rightST.size > 0 ) { stack.push( current.node.rightST ); }
	     if ( current.node.leftST.size > 0) { stack.push( current.node.leftST ); }
         return current.node.obj;
      }

      public void remove () { // overrides java.util.Iterator
         throw new UnsupportedOperationException();
      }

   }

   // Helper class representing a inorder iterator for non-empty trees:

   class InorderIterator implements java.util.Iterator {

      private java.util.Stack<BinaryTree> stack;
      private BinaryTree p;
   
      public InorderIterator ( BinaryTree bt ) {
         stack = new java.util.Stack<BinaryTree>();
	     p = bt;
		 while ( p.size > 0 ) { stack.push ( p ); p = p.node.leftST; }
      }

      public boolean hasNext () { 
         return ! ( p.size == 0 && stack.empty() );
      }

      public Object next () {
	     if ( stack.empty() ) { throw new java.util.NoSuchElementException(); }
		 p = stack.pop();
	     Object result = p.node.obj;
         p = p.node.rightST;
         while ( p.size > 0 ) { stack.push ( p ); p = p.node.leftST; }
	     return result;
      }

      public void remove () {
         throw new UnsupportedOperationException();
      }
   }
}

